package demo1;

import java.util.HashMap;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-08-22
 * Time: 19:35
 */
public class TestDemo {

    //给你字符串数组代表每个字符串代表一张贴纸,将字符串进行切割,然后拼接成target字符串
    //求得贴纸的最小张数

    //暴力递归
    public static int minStickers(String[] stickers, String target) {
        return  process(stickers,target)==Integer.MAX_VALUE ?-1
                : process(stickers,target);
    }

    public static int process(String[] stickers,String target){
        if(target.length()==0){
            //如果这个被剪的没有就最小张数就为0
            return 0;
        }
        int min = Integer.MAX_VALUE;
        //每一张贴纸都作为第一张试试
        for(String first : stickers){
            String rest = minus(target,first);
            if(rest.length()!=target.length()){
                //如果修剪过的剩余的贴纸与target不相等说明可以进行修剪
                min = Math.min(min,process(stickers,rest));
            }
        }
        return min == Integer.MAX_VALUE ? Integer.MAX_VALUE : min+1;
    }

    public static String minus(String s1,String s2){
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int[] count = new int[26];
        for(char c1 : str1){
            count[c1-'a']++;
        }
        for(char c2 : str2){
            count[c2-'a']--;
        }
        StringBuilder res = new StringBuilder();
        for(int i =0;i<26;++i){
            if(count[i]>0){
                for(int j = 0;j<count[i];++j){
                    res.append((char)(i+'a'));
                }
            }
        }
        return res.toString();
    }

    //构造词频--使用剪枝优化

    public static int minStickers1(String[] stickers, String target) {
        //将stickers的每一个字符串生成一个二维的词频表
        //每一行代表i位置字符串的词频统计
        int[][] ans = new int[stickers.length][26];
        for(int i = 0;i<stickers.length;++i){
            char[] str = stickers[i].toCharArray();
            for(char c : str){
                ans[i][c-'a']++;
            }
        }
        return process1(ans,target)==Integer.MAX_VALUE ?-1
                : process1(ans,target);
    }
    public static int process1(int[][] stickers,String target){
        if(target.length()==0){
            return 0;
        }
        //对target做词频统计
        int[] tarCount = new int[26];
        char[] t = target.toCharArray();
        for(char c : t){
            tarCount[c-'a']++;
        }
        int N = stickers.length;
        int min = Integer.MAX_VALUE;
        for(int i =0;i<N;++i){
            int[] sticker = stickers[i];
            //剪枝--字符串中有与target的第一个字符相同的进行修剪
            if(sticker[t[0]-'a']>0){
                StringBuilder res = new StringBuilder();
                for(int j =0; j < 26;++j){
                    if(tarCount[j]>0){
                        int nums = tarCount[j] - sticker[j];
                        for(int k =0;k<nums;++k){
                            res.append((char)(j+'a'));
                        }
                    }
                }
                min = Math.min(min,process1(stickers,res.toString()));
            }
        }
        return min == Integer.MAX_VALUE ? Integer.MAX_VALUE : min+1;
    }


    public static int minStickers3(String[] stickers, String target) {
        //将stickers转化成一个二维的  每一行代表i下标字符串的词频统计
        int[][] count = new int[stickers.length][26];
        for(int i =0;i<stickers.length;++i){
            char[] str = stickers[i].toCharArray();
            for(char c : str){
                count[i][c-'a']++;
            }
        }
        HashMap<String,Integer> dp = new HashMap<>();
        //dp.put("",0);
        int ans = process3(count,target,dp);
        return ans==Integer.MAX_VALUE ? -1 : ans;
    }

    public static int process3(int[][] stickers,String target,HashMap<String,Integer> dp){
        if(dp.containsKey(target)){
            return dp.get(target);
        }
        //将target--->做词频统计
        int[] tarCount = new int[26];
        char[] t = target.toCharArray();
        for(char c : t){
            tarCount[c-'a']++;
        }
        int min = Integer.MAX_VALUE;
        for(int i=0;i<stickers.length;++i){
            int[] sticker = stickers[i];
            //做剪枝
            if(sticker[t[0]-'a']>0){
                StringBuilder res = new StringBuilder();
                for(int j =0;j<26;++j){
                    if(tarCount[j]>0){
                        int nums = tarCount[j]-sticker[j];
                        for(int k =0;k<nums;++k){
                            res.append((char)(j+'a'));
                        }
                    }
                }
                min = Math.min(min,process3(stickers,res.toString(),dp));
            }
        }
        int ans = min==Integer.MAX_VALUE ? Integer.MAX_VALUE+0 : min+1;
        dp.put(target,ans);
        return ans;
    }


    public static void main(String[] args) {
//        ["with","example","science"]
//        "thehat"
        String[] stickers = {"with","example","science"};
        String target = "thehat";
      //  System.out.println(minStickers(stickers, target));
        System.out.println(minStickers3(stickers, target));
    }



}
